1. Technical Field
The present invention relates generally to the storage and display of computer graphics. Specifically, the present invention manipulates and displays large sets of three-dimensional data using several discrete computer systems which operate together.
2. Description of the Related Art
Computers are often used for the manipulation and display of graphical data, and computer users expect increasing levels of sophistication and realism in these systems. Interactive graphics have often been limited to two dimensional (2D) images and animated sequences, because the storage and computational requirements may be met with a typical computer system. Now, however, interaction with three dimensional (3D) scenes is utilized in many applications. These 3D scenes are often more difficult to manage than 2D graphics because of the storage and computational requirements necessary to properly view a 3D scene. Factors such as geometry and lighting calculations, applications of textures and other surface features must all be analyzed to accurately depict the 3D scene. Both the computation and storage of these elements are demanding of computer systems. However, due to advances in computer technology, modest amounts of 3D data can be rendered into images and displayed using generally available personal computers. But, very high-quality 3D scenes can require the storage and manipulation of more 3D data than a single personal computer can efficiently handle. Thus, the development of computer systems which can manipulate and display ever larger amounts of 3D data for generating high-quality graphic images is ongoing.
One solution has been to improve the hardware and software that converts 3D scene data into a sequence of images for display. However, the “3D rendering algorithms” used to accomplish this task are relatively advanced and only modest improvements have occurred in the past few years. The integrated circuits used for rendering have made significant advances, along with the progress of integrated circuits in general, but each new generation yields only incremental performance increases.
Another approach to improve the performance of 3D rendering algorithms relates to displaying only a portion of the 3D data at one time. By omitting large parts of data from the rendering process, the algorithm may execute more quickly. However, systems which rely solely on this method often are forced to omit relevant parts of the 3D scene. In essence, a “close up” view of one portion of the 3D scene is all that can be displayed. This characteristic is often unacceptable for users.
Multiresolution modeling represents yet another approach for efficiently manipulating and displaying 3D data sets. Multiresolution modeling techniques operate on the principle that some elements that make up a 3D scene are of less importance than others. For example, items in the background of a 3D scene might be represented in less detail than items in the foreground. These techniques correspond to the way people view the world around them. People perceive objects located far away as being generally smaller and containing less detail as compared to nearby objects. Computer systems employing multiresolution modeling techniques generally take advantage of this characteristic of human perception by illustrating objects located in the background of a 3D scene with less detail than those located in the foreground.
For example, a high-resolution image of a house could contain data which represents the contours of each brick, the leaves of shrubs in front of the house, the individual shingles on the roof, and so on. In a 3D scene, if the house is located in the immediate foreground, all of the data representing the details described above may have to be recalled from some storage device (e.g., a hard disk or CD-ROM), transmitted to the graphics processor, and then rendered. On the other hand, if the house were in the far background, the bricks could be represented as simple rectangles of a single color, without any contours, and the shrubs and roof could be similarly simplified. The amount of data required to represent a low-resolution 3D model of the house is much less than is required to represent the high-resolution 3D model. Processing lower resolution 3D data results in faster rendering of the data into images, as the smaller data set size allows for a lightened computational load for the computer system.
Multiresolution modeling appears to be an efficient method for lessening the data sizes used to render, however, it does have its drawbacks. These drawbacks tend to adversely impact either disk storage space or processing resources. FIG. 1 illustrates an example of how implementing multiresolution modeling on a computer system can consume large amounts of the computer's data storage (e.g., disk space or RAM). As shown in FIG. 1, several versions of 3D data representing the house discussed above are stored at varying levels of detail (LOD). The model designated as LOD[0] contains all of the details of the house, while model LOD[8] is a highly simplified model, with few detail. Models LOD[1] through LOD[7] contain intermediate levels of detail. When the 3D model of the house is required for the rendering of an image, workstation 120 determines the appropriate detail needed for the rendered house to have good visual qualities, then recalls the data representing the house at the appropriate LOD from storage 110. Next, workstation 120 uses this LOD model of the house in its graphics subsystem, which renders it to display 130. The problem with this method is that multiple data sets representing the same house at varying LOD have to be stored in storage 110. These redundant models consume more storage space than a single model and therefore represent an inefficient aspect of this implementation of the multiresolution modeling technique. The storage penalty is particularly large if many LOD versions are stored for higher visual quality.
Some more sophisticated multiresolution imaging techniques use what are known as progressive techniques. Progressive techniques allow a single high-resolution 3D data set to be transformed into other data sets with an almost unlimited LOD. In particular, Hughues Hoppes' Progressive Mesh (PM) represents an advanced multiresolution progressive technique. In 3D graphics, vertices in 3D spaces describe polygons. Polygons are the basic building blocks in traditional 3D graphics. PM techniques generally operate on the collection of vertices that describe the surfaces of objects.
Using PM techniques, a 3D data set representing a complex object is converted into a simplified form made of many fewer vertices and a list (or stream) of “mesh operations” that can extend this data back into the complete 3D data set. The more a computer system utilizes the stream, the more details of the object represented by the 3D data will be available. A short prefix of the stream generates a low LOD version of the object, while a longer prefix of the stream generates a higher LOD version of the object. One benefit of PM techniques is that redundant copies of the model do not have to be stored at varying LOD, as the system can generate an LOD model needed dynamically. However, PM techniques generally require a significant amount of processing resources to convert a model from one LOD to another.
Thus, it would be desirable to create a computer system which uses PM techniques for high visual quality given the constraints of available hardware. However, such a system should not suffer excessive performance penalties associated with constructing lower-resolution data sets from the high-resolution sets, or the benefit of multiresolution modeling is lost.